package org.leetcode.easy.leetcode543;

import org.leetcode.TreeNode;

public class Solution {

    public int diameterOfBinaryTree2(TreeNode root){

        getDepth(root);
        return res;
    }

    private int getDepth(TreeNode root){
        if (root==null){
            return 0;
        }

        int left = getDepth(root.left);
        int right = getDepth(root.right);

        res = Math.max(res,left+right+1);

        return Math.max(left,right)+1;

    }

    int res;
    public int diameterOfBinaryTree(TreeNode root) {

       res = 1;

       depth(root);

        return res-1;
    }


    private int depth(TreeNode node)
    {
        if (node==null)
        {
            return 0;
        }

        int left = depth(node.left);
        int right = depth(node.right);

        res =Math.max(res,left+right+1);

        return Math.max(left,right)+1;
    }
}
